package Leetcode.数组字符串;

/**
 * @ClassName 递增的三元子序列
 * @since: 2023/8/5 15:02
 * @auth: kirito
 * @description:
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 *
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，
 * 使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 *
 * 最长公共子序列问题简化版
 **/
public class 递增的三元子序列 {
    /**
     1.小于3  肯定不存在 直接返回
     2.从左往右记录一个当前位置之前的最小的数组
        从右往左记录一个当前位置之前最大的数组
     3.然后遍历一次  比较min 和max数组
        如果i索引处的值比min大 比max小  则存在true，否则false
     */
    public boolean increasingTriplet1(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }

        int[] leftMin = new int[n];
        leftMin[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }

        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) {
                return true;
            }
        }
        return false;
    }
    /*第二种方法用人话说就是：
赋初始值的时候，已经满足second > first了，现在找第三个数third
(1) 如果third比second大，那就是找到了，直接返回true
(2) 如果third比second小，但是比first大，那就把second指向third，然后继续遍历找third
(3) 如果third比first还小，那就把first指向third，然后继续遍历找third
（这样的话first会跑到second的后边，但是不要紧，因为在second的前边，老first还是满足的）
    * */
    public static boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] a = {20,100,10,12,5,13};
        System.out.println(increasingTriplet(a));

    }
}
